#include <stdio.h>

#define ARRAYSIZE 16

unsigned long int next = 1;

int rand(void);
void srand(unsigned int seed);
void shellsort(int v[], int n);
void printarray(int v[]);

int main()
{
    int i, v[ARRAYSIZE];

    for (i = 0; i < ARRAYSIZE; i++)
    {
        srand(next);
        v[i] = rand();
    }

    printf("before: ");
    printarray(v);

    shellsort(v, ARRAYSIZE);

    printf("after: ");
    printarray(v);

    return 0;
}

int rand(void)
{
    next = next * 1103512545 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for (gap = n / 2; gap > 0; gap /= 2)
    {
        for (i = gap; i < n; i++)
        {
            for (j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap)
            {
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}

void srand(unsigned int seed) { next = seed; }

void printarray(int v[])
{
    for (int i = 0; i < ARRAYSIZE; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}
